Ваша задача
очень простая и даже без большой легенды: просто нужно найти максимум на
отрезке.
Вход. Сначала подаётся количество чисел n (1 ≤ n ≤ 105)
в массиве. В следующей строке заданы n
чисел – исходный массив a1,
a2, ..., an (-109 ≤ ai ≤ 109).
Следующая строка содержит количество запросов q (1 ≤ q ≤
5·105). Каждая из следующих q
строк содержит по два натуральных числа l
и r (1 ≤ l, r ≤ n) – отрезок, на котором следует найти
максимум.
Выход. Для каждого запроса выведите максимум на заданном
отрезке.
|
Пример
входа |
Пример
выхода |
|
10 5 1 2 8 7 6
10 7 5 6 8 1 10 5 10 1 5 2 6 2 3 7 7 7 8 5 9 |
10 10 8 8 2 10 10 10 |
структуры
данных – RMQ
Поскольку
модификация элементов отсутствует, то задачу можно решить при помощи RMQ (Range
Max Query).
Время
предварительной обработки входного массива и построения RMQ массива равно O(nlogn),
а время выполнения запроса RMQ(i, j) константно и составляет O(1).
Входную
последовательность ai
длины n ≤ 105 храним
в массиве а. Объявим массив mas для выполнения предобработки данных.
#define MAX 100010
#define LOGMAX 17
int mas[MAX][LOGMAX];
int a[MAX];
Заполняем массив
m так, чтобы mas[i][j] = max(bi, bi+1,
…, bi+2^j-1).
void Build_RMQ_Array(int *b)
{
int i, j;
for (i = 1; i
<= n; i++) mas[i][0] = b[i];
for (j = 1; 1
<< j <= n; j++)
for (i = 1;
i + (1 << j) - 1 <= n; i++)
mas[i][j] = max(mas[i][j - 1], mas[i + (1
<< (j - 1))][j - 1]);
}
Выполняем запрос RMQ(i, j),
возвращающий максимальный элемент в подмассиве a[i…j].
int RangeMaxQuery(int i, int j)
{
int temp, k =
0;
if (i > j)
temp = i, i = j, j = temp;
while ((1
<< (k + 1)) <= j - i + 1) k++;
return
max(mas[i][k],mas[j - (1<<k) + 1][k]);
}
Основная часть
программы. Читаем входные данные.
scanf("%d",&n);
for(i = 1; i <= n; i++) scanf("%d",&a[i]);
Совершаем препроцессинг. По массиву a
строим массив mas.
Build_RMQ_Array(a);
Последовательно выполняем запросы и
выводим их результаты.
scanf("%d",&q);
for(i = 0; i < q; i++)
{
scanf("%d
%d",&u,&v);
printf("%d\n",RangeMaxQuery(u,v));
}